package basic.study.algorithms.solution.recall;

/**
 * @author Kevin
 * @date 2020/4/24 12:28
 * 问题描述：硬币分别有面值分别为1，5, 10, 25四种面值。输入一个整数n，用这些硬币组合成数值n，问有多少种组合方式？
 * 方法1：暴力   方法2：递归
 */

import java.util.Scanner;

public class Coin {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = {1,5,10,25};
        System.out.println(solve(n, a, 3));
    }

    private static int solve(int n, int[] a, int m) {
        int res = 0;
        if(m==0) return 1;
        if(n==0) return 1;
        for(int i=0; i*a[m]<=n; i++){
            res = res + solve(n-i*a[m], a, m-1);
        }
        return res;
    }
}
